/*
https://leetcode-cn.com/problems/jump-game-ii/solution/tiao-yue-you-xi-ii-by-leetcode-solution/
 */
public class Solution45 {
    public int jump(int[] nums) {
        if (nums.length==1){
            return 0;
        }
        int cur=0;
        int time=0;
        while (cur<nums.length){
            if (cur+nums[cur]>=nums.length-1){
                return time+1;
            }
            int l=cur;
            int max=0;
            for (int i=1;i<=nums[cur];i++){
                if (cur+i+nums[cur+i]>l){
                    l=cur+i+nums[cur+i];
                    max=cur+i;
                }
            }
            cur=max;
            time++;
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(new Solution45().jump(new int[]{2,3,1,1,4}));
    }
}
